package 左哥算法.ch06二叉树;

import org.junit.Test;

import java.util.*;

public class B树 {

    /**
     * 以下是核心代码
     */
    static class BTree {
        int degree; // 树的度数，决定节点的最多能有多少子节点
        Node root = new Node(null);

        public BTree(int degree) {
            this.degree = degree;
        }

        /**
         * 插入一个新的key到B树中
         * 1. 查找key应插入的节点
         * 2. 将key插入节点，如果节点元素数量超过限制，则进行分裂
         *
         * @param key 要插入的值
         */
        public void add(int key) {
            if (root.elements.isEmpty()) { // 如果根节点为空，直接插入根节点
                root.elements.add(new Element(key, 1));
                return;
            }
            Node node = search(root, key); // 查找key的插入位置
            int i = 0;
            for (; i < node.elements.size(); i++) {
                Element e = node.elements.get(i);
                if (e.v == key) { // 如果key已存在，增加计数
                    e.cnt++;
                    return;
                } else if (e.v > key) {
                    break;
                }
            }
            node.elements.add(i, new Element(key, 1)); // 插入key到节点中
            if (node.elements.size() >= degree) { // 如果节点超载，进行分裂
                split(node);
            }
        }

        /**
         * @param cur
         */
        private void split(Node cur) {
            int m = degree >> 1; // 中间元素的下标
            Element me = cur.elements.get(m); // 中间元素
            Node p = cur.parent;

            /*如果是根节点溢出，则诞生一个新的根节点*/
            if (cur == root) {
                p = new Node(null);
                p.children.add(cur);
                cur.parent = p;
                root = p;
            }

            // 将当前节点拆分为左右节点
            Node left = new Node(p);
            Node right = new Node(p);
            /*分割出左部分和右部分元素，不包含中间元素*/
            left.elements = new ArrayList<>(cur.elements.subList(0, m));
            right.elements = new ArrayList<>(cur.elements.subList(m + 1, cur.elements.size()));

            // 处理子节点
            if (!cur.children.isEmpty()) {
                /*分割出左部分和右部分子节点,不需要舍弃中间节点*/
                int mid = (cur.children.size() - 1 >> 1) + 1;   /*向上取整*/
                left.children = new ArrayList<>(cur.children.subList(0, mid));
                right.children = new ArrayList<>(cur.children.subList(mid, cur.children.size()));
                /*将左部分孩子和右部分孩子parent指向分裂出来的节点*/
                for (Node c : left.children) c.parent = left;
                for (Node c : right.children) c.parent = right;
            }

            List<Element> pes = p.elements;
            List<Node> children = p.children;
            /*找到中间元素在父节点的位置*/
            for (int pi = 0; pi < children.size(); pi++) {
                if (children.get(pi) == cur) {
                    pes.add(pi, me); // 插入中间元素到父节点
                    children.remove(pi);   // 删除父节点对当前节点的引用
                    /*将left和right插入到父亲中*/
                    children.add(pi, left);
                    children.add(pi + 1, right);
                }
            }

            // 递归向上处理溢出
            if (pes.size() >= degree) split(p);
        }

        /**
         * 删除一个key
         *
         * @param key 要删除的key
         * @return 删除成功返回true，失败返回false
         */
        public boolean del(int key) {
            if (root.elements.isEmpty()) return false;

            Node node = search(root, key);
            Element e = null;

            // 查找元素所在的位置
            int i = 0;
            for (; i < node.elements.size(); i++) {
                e = node.elements.get(i);
                if (e.v == key) {
                    break;
                }
            }
            if (i >= node.elements.size()) return false;  // 未找到
            if (--e.cnt > 0) return true;   // 多次存在，只减少计数

            if (!node.children.isEmpty()) { /*删除非叶子节点*/
                /*找到e的直接前驱*/
                Node pre = node.children.get(i);
                while (!pre.children.isEmpty()) {
                    pre = pre.children.get(pre.children.size() - 1);
                }
                Element preE = pre.elements.remove(pre.elements.size() - 1);

                /*替换掉原来的非叶子节点*/
                node.elements.set(i, preE);
                node = pre;
            } else {    /*删除叶子节点*/
                node.elements.remove(i);
            }
            /*b树中，最少的子节点数是 celi(m/2) 最少的元素是 ceil(m/2)-1*/
            int limit = degree - 1 >> 1;    /*(m-1>>1)+1 是上取整*/
            // 检查并修复节点下溢
            if (node.elements.size() < limit && node != root) {
                slink(node);
            }
            return true;
        }

        /**
         * 处理节点下溢
         *
         * @param node 下溢的节点
         */
        private void slink(Node node) {
            int limit = degree - 1 >> 1;
            Node p = node.parent;
            List<Node> children = p.children;
            // 找到当前节点在父节点children中的位置
            int ci = 0;
            for (; ci < children.size(); ci++) {
                if (children.get(ci) == node) break;
            }
            if (ci != 0) {
                /*从左侧拿*/
                if (children.get(ci - 1).elements.size() > limit) {
                    /*够拿则拿*/
                    takeLeft(p, ci - 1);
                } else {
                    /*不够则合并*/
                    merge(children.get(ci - 1), ci - 1);
                }
            } else {
                /*从右侧拿*/
                if (children.get(ci + 1).elements.size() > limit) {
                    takeRight(p, ci);
                } else {
                    merge(node, ci);
                }
            }
            if (p.elements.size() < limit) {
                if (p == root) {
                    /*如果根节点没有元素了,则让当前节点变为新的根节点*/
                    if (root.elements.isEmpty()) {
                        /*node不一定是根节点，可能是空节点，第一个节点才是根节点*/
                        Node newRoot = children.get(0);
                        newRoot.parent = null;
                        root = newRoot;
                    }
                } else {
                    slink(p);
                }
            }
        }

        /**
         * 从左侧兄弟节点借元素
         */
        private void takeLeft(Node p, int pi) {
            Node left = p.children.get(pi);
            Node right = p.children.get(pi + 1);
            /*左孩子的最后一个节点*/
            Element le = left.elements.remove(left.elements.size() - 1);
            /*用最后的节点替换掉父元素*/
            Element pe = p.elements.set(pi, le);
            /*将父元素放到当前的最左侧*/
            right.elements.add(0, pe);
            if (!left.children.isEmpty()) {
                Node lc = left.children.remove(left.children.size() - 1);
                right.children.add(0, lc);
                lc.parent = right;
            }
        }

        /**
         * @param p：父节点
         * @param pi：父元素的位置
         */
        private void takeRight(Node p, int pi) {
            Node left = p.children.get(pi);
            Node right = p.children.get(pi + 1);

            Element re = right.elements.remove(0);
            Element pe = p.elements.set(pi, re);
            left.elements.add(pe);
            if (!right.children.isEmpty()) {
                Node rc = right.children.remove(0);
                left.children.add(rc);
                rc.parent = left;
            }
        }

        /**
         * 将右侧合并到左侧
         *
         * @param left
         * @param li
         */
        private void merge(Node left, int li) {
            Node p = left.parent;
            /*移除掉父元素中对应的位置*/
            Element e = p.elements.remove(li);
            left.elements.add(e);
            /*移除掉右节点*/
            Node right = p.children.remove(li + 1);
            /*将右节点的元素添加到左节点中*/
            left.elements.addAll(right.elements);
            /*将右节点的孩子添加到左节点中*/
            left.children.addAll(right.children);
            for (Node c : right.children) {
                c.parent = left;
            }
        }

        /**
         * 查找元素是否存在
         */
        public boolean has(int key) {
            Node node = search(root, key);
            for (Element e : node.elements) {
                if (e.v == key) return true;
                if (e.v > key) break;
            }
            return false;
        }

        /**
         * 找到该节点或者最接近的叶子节点
         */
        private Node search(Node curr, int key) {
            if (curr.children.isEmpty()) return curr;

            Node next = curr.children.get(0);
            for (int i = 0; i < curr.elements.size(); i++) {
                Element e = curr.elements.get(i);
                if (e.v == key) return curr;
                if (e.v > key) break;
                /* i+1表示 i位置的右孩子*/
                next = curr.children.get(i + 1);
            }
            return search(next, key);
        }

        /**
         * B树节点，存储元素和下一个节点
         */
        public static class Node {
            Node parent;
            List<Element> elements = new ArrayList<>();
            List<Node> children = new ArrayList<>();

            public Node(Node parent) {
                this.parent = parent;
            }

            @Override
            public String toString() {
                return elements.toString();
            }
        }

        /**
         * 每个节点中的元素
         */
        public static class Element {
            int v, cnt;

            public Element(int v, int cnt) {
                this.v = v;
                this.cnt = cnt;
            }

            @Override
            public String toString() {
                return "{" + "v=" + v + ", cnt=" + cnt + '}';
            }
        }
    }


    /*以下是对数器*/

    static int maxn = (int) 1e3;

    static Random r = new Random();

    @Test
    public void test() {
        int[][] ops = {
                {1, 657, 9},
                {1, 826, 10},
                {1, 117, 3},
                {1, 555, 8},
                {1, 908, 12},
                {1, 146, 4},
                {1, 284, 5},
                {1, 338, 6},
                {1, 835, 11},
                {2, 117, 3},
                {0, 363, 7},
        };
        BTree bTree = new BTree(3);
        int index = 2;
        for (int i = 0; i < ops.length; i++) {
            int op = ops[i][0];
            int v = ops[i][index];
            if (op == 0) {
                System.out.println("has:" + v + "=" + bTree.has(v));
            } else if (op == 1) {
                bTree.add(v);
            } else if (op == 2) {
                System.out.println("del:" + v + "=" + bTree.del(v));
            }
        }
    }

    @Test
    public void test100() {
        int cnt = (int) 1e4;
        int ops = (int) 1e5;
        for (int i = 0; i < cnt; i++) {
            compare(r.nextInt(40) + 3, ops);
//            compare(3, ops);
        }
    }

    /**
     * 用来打印整棵树
     * @param root
     */
    public static void print(BTree.Node root) {
        Queue<BTree.Node> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                BTree.Node poll = queue.poll();
                System.out.print(poll.elements + "\t");
                queue.addAll(poll.children);
            }
            System.out.println();
        }
    }

    @Test
    public void test2() {
        Ans ans = new Ans();
        ans.has(857);
        ans.add(612);
        ans.has(461);
        ans.has(135);
        ans.has(207);
        ans.add(979);
        System.out.println(ans.has(857));
    }

    public static void compare(int m, int cnt) {
        /*3位置用来做离散化*/
        int[][] ops = new int[cnt][3];
        Ans ans = new Ans();
        BTree bTree = new BTree(m);
        try {
            for (int i = 0; i < ops.length; i++) {
                int op = r.nextBoolean() ? 1 : r.nextInt(3);
                int v = r.nextInt(maxn);
                ops[i][0] = op;
                ops[i][1] = v;
                switch (op) {
                    case 0: {
                        boolean a = ans.has(v);
                        boolean b = bTree.has(v);
                        if (a != b) {
                            throw new RuntimeException("查询发生错误:预期:" + a + ";\t 结果:" + b);
                        }
                        break;
                    }
                    case 1: {
                        ans.add(v);
                        bTree.add(v);
                        break;
                    }
                    case 2: {
                        v = ops[r.nextInt(Math.max(1, i))][1];
                        ops[i][1] = v;
                        boolean a = ans.del(v);
                        boolean b = bTree.del(v);
                        if (a != b) {
                            throw new RuntimeException("删除发生错误:预期:" + a + ";\t 结果:" + b);
                        }
                        break;
                    }
                }
            }
        } catch (Exception e) {
            int[] sort = new int[cnt];
            for (int j = 0; j < cnt; j++) {
                sort[j] = ops[j][1];
            }
            Arrays.sort(sort);
            for (int[] o : ops) {
                o[2] = Arrays.binarySearch(sort, o[1]) + 1;
                System.out.println("{" + o[0] + "," + o[1] + "," + o[2] + "},");
            }
            throw e;
        }
    }

    static class Ans {
        int[] cnt = new int[maxn + 10];

        public void add(int k) {
            cnt[k]++;
        }

        public boolean has(int k) {
            return cnt[k] != 0;
        }

        public boolean del(int k) {
            if (cnt[k] <= 0) {
                return false;
            }
            cnt[k]--;
            return true;
        }
    }

}
